package com.haohuo.question3;

import java.util.Random;

/**
 * 收入
 * note： 无序整数列表，返回最大的K个数问题
 **/
public class TopIncome {

    // 测试数据
    public static void main(String[] args) {
        int[] elements = {1111, 11, 3111, 611, 822, 13000, 100, 5099, 995, 9033};
        int[] result = new TopIncome().getTopMaxByQuickSort(elements, 9);
        for (int element : result) {
            System.out.println(element);
        }
    }

    /**
     * 返回最大的K个数（利用快速排序）
     *
     * @param elements
     * @param k
     * @return
     */
    public int[] getTopMaxByQuickSort(int[] elements, int k) {
        int[] result = new int[k];
        if (null == elements || k == 0 || elements.length < k) {
            return result;
        }
        quickSelect(elements, 0, elements.length - 1, k);
        for (int i = 0; i < k; i++) {
            result[i] = elements[i];
        }
        return result;
    }

    /**
     * 快速选择最大的K个数
     * 利用快速排序的分片思想，比基准数大的都在一侧，比基准数小的都在一侧
     * 由于输出不需要排序，不需要在对分片之后的数据继续分片
     *
     * @param sourceArray    需要排序的数组
     * @param leftIndex      开始下标
     * @param rightIndex     结束下标
     * @param toSelectLength 要选择的长度
     */
    private void quickSelect(int[] sourceArray, int leftIndex, int rightIndex, int toSelectLength) {
        if (leftIndex >= rightIndex || rightIndex + 1 == toSelectLength) {
            return;
        }
        int pos = partition(sourceArray, leftIndex, rightIndex);
        int sortedLength = pos - leftIndex + 1;
        if (sortedLength == toSelectLength) {
            return;
        } else if (sortedLength > toSelectLength) {
            quickSelect(sourceArray, leftIndex, pos - 1, toSelectLength);
        } else if (sortedLength < toSelectLength) {
            quickSelect(sourceArray, pos + 1, rightIndex, toSelectLength - sortedLength);
        }
    }


    /**
     * 分片：从大到小
     *
     * @param sourceArray
     * @param leftIndex
     * @param rightIndex
     * @return
     */
    private int partition(int[] sourceArray, int leftIndex, int rightIndex) {
        // 随机分片（）
        int pivotIndex = new Random().nextInt(rightIndex - leftIndex + 1) + leftIndex;
        swap(sourceArray, pivotIndex, rightIndex);
        int pivot = sourceArray[rightIndex];

        int swapIndex = leftIndex - 1;
        for (int i = leftIndex; i <= rightIndex; i++) {
            if (sourceArray[i] > pivot) {
                swapIndex = swapIndex + 1;
                swap(sourceArray, swapIndex, i);
            }
        }
        swap(sourceArray, swapIndex + 1, rightIndex);
        // 返回最后一次交换的坐标：左边全部为最大的n个数据
        return swapIndex + 1;
    }

    /**
     * 数组元素交换
     *
     * @param sourceArray
     * @param i
     * @param j
     */
    private void swap(int[] sourceArray, int i, int j) {
        if (i != j) {
            int temp = sourceArray[i];
            sourceArray[i] = sourceArray[j];
            sourceArray[j] = temp;
        }
    }

}
